1. Field of the Invention
This invention relates to signal processing, in general, and to image and/or speech processing, in particular. More specifically, the invention relates to a non-linear filter and method usable for rank-order filtering and, with an appropriate choice of rank, for median filtering.
2. Description of the Prior Art
Rank-order filtering is widely used in speech and image processing. It is a technique for performing non-linear smoothing of a single- or multi-dimensional signal consisting of discrete samples. An output sample is generated by the filter for each such input sample. Each input sample and some preselected number of neighboring samples are collected in a sliding window. The output value is the n.sup.th lowest sample value within the window, where n is the rank order of the filter. When n is the median sample (i.e., there are just as many samples in the window having greater value than the median sample as there are samples in the window of lower value), the rank-order filter is referred to as a median filter. The resulting output sequence for filtered samples tends to follow polynomial trends in the input sample sequence, while filtering out sharp discontinuities of short duration. That is, this type of filtering is particularly useful for reducing the effect of highly transient noise "spikes" in the signal being processed.
Numerous designs exist or have been proposed in the prior art for both one-dimensional and two-dimensional rank-order filters, especially median filters. Such filtering has generally proven to consume significant processing time, making implementation more difficult.
The literature contains analyses of various architectures for rank-order filtering, with particular emphasis on the complexity and speed of processing, including the type and number of operations which must be performed and the number of clock cycles required. Attention has previously been directed to the fact that VLSI technology offers system designers a high potential for performing parallel operations, which potential may be exploited for median filters. However, prior efforts in this direction leave room for much improvement.
Oflazer discusses a single chip one-dimensional median filter using an odd/even transposition sort as the high level algorithm and systolic data flow concepts at the bit level to achieve high throughput. K. Oflazer, "Design and Implementation of a Single Chip 1-D Median Filter," I.E.E.E. Trans. on Acoustics, Speech and Sig. Proc., Vol. ASSP-31, No. 5, October 1983, pp. 1165-1168. He notes that the network implementing the pipelined odd/even transposition sort requires chip area proportional to the square of the window size, thus his design is suitable for median filters with small window sizes only.
Huang et al. have described a two-dimensional median filter structure and algorithm and an associated method which are based on storing the grey level histogram of the MN picture elements in a window of M.times.N numbers, and updating the histogram as the window moves. T. S. Huang et al., "Fast Two-Dimensional Median Filtering Algorithm," I.E.E.E. Trans. on Acoustics, Speech on Sig. Proc., Vol. ASSP-27, No. 1, February 1979, pp. 13-18. According to Huang et al., the histogram needs only to be partially updated when the window is moved. By observing how many picture elements fall above and below the previous median value, that prior median can be simply adjusted each time the window is moved, to the correct new median value, by stepping upward or downward in the histogram. The algorithm requires a fast RAM for the histogram; but the time for the stepping procedure is data dependent. Consequently, one must allow for a worst case number of steps equal to the number of "buckets" in the histogram. This algorithm requires approximately 2N+10 comparisons to obtain the median of each MN set of samples.
Danielsson has suggested that the median, or any other rank-order value, can be found by collecting a set of histograms. P. Danielsson, "Getting the Median Faster," Computer Graphics and Image Processing, Vol. 17, pp. 71-78 (1981). This method, however, results in a rather cumbersome histogram collection process. In Danielsson's paper, he observes that Kruse has suggested that instead of arranging for histograms, one should use the arguments repeatedly, comparing them to a successively refined median. Unfortunately, as Danielsson observed, this requires fetching each argument "k" times, where k is the number of Danielsson-type histograms and the number of bits per sample.
The present invention has as its principal objective the provision of an improved architecture and method for rank-order filtering.
Further an object of the invention is to provide an improved method and apparatus for median filtering.
Yet another object of the invention is to provide a rank-order filtering architecture which is efficient and facilitates integrated circuit implementation using a silicon compiler.
Still another object of the invention is to provide such an architecture which exhibits a linear relationship between window size (i.e., the number of samples in the window as well as the number of bits in each sample) and required chip area.